public class Solution1312 {

    public int minInsertions(String s) {
        int[][] f=new int[s.length()][s.length()];
        for (int i=s.length()-1;i>=0;i--){
            f[i][i]=0;
            for (int j=i+1;j<s.length();j++){
                f[i][j]=Integer.MAX_VALUE;
                if (s.charAt(i)==s.charAt(j)){
                    f[i][j]=f[i+1][j-1];
                }
                f[i][j]=Math.min(f[i][j],f[i+1][j]+1);
                f[i][j]=Math.min(f[i][j],f[i][j-1]+1);
            }
        }
        return f[0][s.length()-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1312().minInsertions("leetcode"));
    }


}
